排列序列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321”

给定 n 和 k，返回第 k 个排列。

示例 1：

1
2
输入：n = 3, k = 3
输出："213"

示例 2：

1
2
输入：n = 4, k = 9
输出："2314"

示例 3：

1
2
输入：n = 3, k = 1
输出："123"

提示：

  • 1 <= n <= 9
  • 1 <= k <= n!

代码：

65%45%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> ls= new ArrayList<Integer>();
        //初始化数组
        for(int i=1;i<n+1;i++)
            ls.add(i);
        //
        StringBuffer sb=new StringBuffer();
        //next的意思是下一次循环需要找的排序号
        int next=k;
        for(int i=n-1;i>0;i--)
        {
            int f=fact(i);
            int index=next/f;
            next=next%f;
            if(next==0) {
                index--;
                next=f;
            }
            sb.append(ls.remove(index));
        }
        sb.append(ls.remove(0));
        return sb.toString();
    }
    //每个数其实也只会算一遍，所以没有必要弄个阶乘数组
    public int fact(int x)
    {
        int max=1;
        if(x==0||x==1)return 1;
        if(x<0)return -1;
        for(int i=x;i>=1;i--)
            max*=i;
        return max;
    }
}